package part2;


/**
 * @Author: shaochong
 * @Date: 2021/8/15
 * @Description:将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
 */
public class Solution21 {
    static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }

        ListNode f1 = new ListNode(0, l1);
        ListNode f2 = new ListNode(0, l2);

        ListNode t1 = f1;
        ListNode t2 = f2;

        while (t2.next != null && t1.next != null) {
            // t2插入t1,t1不动
            if (t2.next.val < t1.next.val) {
                // 临时保存此节点
                ListNode t = t2.next;
                // 在t2上删除这个节点
                t2.next = t2.next.next;

                // 将这个节点放到t1 t1.next前面
                t.next = t1.next;
                t1.next = t;
            } else {
                // t1后移
                t1 = t1.next;
            }
        }
        if (t2.next != null) {
            t1.next = t2.next;
        }
        return f1.next;
    }

    public static ListNode mergeTwoLists2(ListNode l1, ListNode l2) {
        ListNode prehead = new ListNode(-1);

        ListNode prev = prehead;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val ) {
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }
        prev.next = l1 == null ? l2 : l1;
        return prehead.next;
    }


        public static void main(String[] args) {
        ListNode n1 = new ListNode(2, null);
//        ListNode n2 = new ListNode(2, null);
//        ListNode n3 = new ListNode(4, null);
//        n1.next = n2;
//        n2.next = n3;
        
        ListNode b1 = new ListNode(1, null);
//        ListNode b2 = new ListNode(3, null);
//        ListNode b3 = new ListNode(4, null);
//        b1.next = b2;
//        b2.next = b3;
        
        ListNode ans = mergeTwoLists(n1, b1);
        System.out.println(ans.val);
    }
}
